package graph.unweighted.euler.hierholzer;

import java.util.ArrayList;
import java.util.Stack;

import graph.unweighted.CandyGraph;
import graph.unweighted.dfs.connectedComponent.CandyConnectedComponent;

/**
 * 
 * @Title: CandyEulerLoop.java 
 * @Package graph.euler 
 * @Description: 求解无向图的欧拉回路
 * @author CandyWall   
 * @date 2021年1月19日 下午8:30:06 
 * @version V1.0
 */
public class CandyEulerLoop {
    private CandyGraph graph;

    public CandyEulerLoop(CandyGraph graph) {
        if(graph.isDirected()) {
            throw new IllegalArgumentException("该类只能求解无向图的欧拉回路！");
        }
        this.graph = graph;
    }
    
    public boolean hasEurlerLoop() {
        CandyConnectedComponent connectedComponent = new CandyConnectedComponent(graph);
        if(connectedComponent.getConnectedComponentCount() > 1) {
            return false;
        }
        
        for(int v = 0; v < graph.getVertex_num(); v++) {
            if(graph.getDegree(v) % 2 != 0) {
                return false;
            }
        }
        
        return true;
    }
    
    /**
     * 获取欧拉回路
     * @return
     */
    public ArrayList<Integer> getEurlerLoop() {
        ArrayList<Integer> loop = new ArrayList<>();
        // 判断是否存在欧拉回路
        if(!hasEurlerLoop()) {
            return loop;
        }
        Stack<Integer> stack = new Stack<>();
        CandyGraph clonedGraph = (CandyGraph) graph.clone();
        int curv = 0;
        stack.push(curv);
        while(!stack.isEmpty()) {
            if(clonedGraph.getDegree(curv) != 0) {
                stack.push(curv);
                int w = clonedGraph.adjacentVertexes(curv).iterator().next();
                clonedGraph.removeEdge(curv, w);
                curv = w;
            }
            // 找到了一个环
            else {
                loop.add(curv);
                curv = stack.pop();
            }
        }
        
        return loop;
    }
    
    public static void main(String[] args) {
        CandyGraph graph = new CandyGraph("testData/graph/euler/hierholzer/graph.txt");
        CandyEulerLoop eulerLoop = new CandyEulerLoop(graph);
        System.out.println("是否有欧拉回路：" + eulerLoop.hasEurlerLoop());
        System.out.println("欧拉回路：" + eulerLoop.getEurlerLoop());
    }
    
}
